1. Field of the Invention
The present invention relates generally to a Mobile Ad hoc Network (MANET), and in particular, to a mobile ad hoc network capable of efficiently discovering and setting up a route from a source node to a destination node, and a route discovery method using the same.
2. Description of the Related Art
A mobile ad hoc network (MANET) refers to a network capable of transferring data between mobile nodes without a communication infra-structure. The mobile ad hoc network technology has been sporadically developed over 20 years. In the early 1970's, radio network technology called Mobile Packet Radio was developed, and since then, it has been applied to various radio physical layer systems such as a diffused infrared system. Fundamentally, the mobile ad hoc network technology makes it possible to form systems unique to mobile nodes. Therefore, the mobile ad hoc network technology is suitable for independent operation of communication networks.
The mobile ad hoc network technology has a self-forming, self-healing network structure adaptable to situations in which data is rapidly spreading and mobility of the communication network's nodes and a traffic transmission condition are subject to frequent change. The mobile ad hoc network is best characterized in that it requires a minimized fixed infra-structure. Other characteristics of the mobile ad hoc network include a relatively frequent change in distributed peer-to-peer mode, multi-hop routing and node arrangement.
The mobile ad hoc network technology can include the Defense Advanced Research Projects Agency's (DARPA's) Packet Radio Network and Survivable Adaptive Network (SURAN) programs developed in the 1970's and 1980's. Although the mobile ad hoc network technology is mainly applied to military tactical communications, it can also be applied to natural disasters, legal execution procedures, and commercial and educational sensor networks. The mobile ad hoc network is roughly comprised of application software, mobile routing, and transport, medium access control (MAC) and physical layers. Among others, the mobile routing and the MAC and physical layers are the core technology of the mobile ad hoc network.
Currently, various technologies have been proposed as the mobile ad hoc network technologies. Table 1 below shows mobile ad hoc network technologies classified according to routing protocol.
TABLE 1Pro-active ProtocolsRe-active ProtocolsClustering Routing(table-driven)(on-demand)ProtocolsDSDV (DestinationDSR (Dynamic SourceZRP (Zone RoutingSequenced DistanceRouting)Protocol)Vector, 1994)AODV (Ad hoc On-OLSR (Optimized LinkWRP (Wirelessdemand Distance Vector)State Routing)Routing Protocol,TORA (TemporallyCEDAR (Core1996)Ordered RoutingExtraction DistributedGSR (Global StateAlgorithm)Ad hoc Routing)Routing, 1998)ABR (Associativity-CBRP (Cluster BasedFSR (Fisheye StateBased Routing)Routing Protocol)Routing, 1999)
With the recent development of applicable commercial radio communication technology, many efforts are being made to achieve commercial standardizations, such as HiperLAN (High Performance Radio Local Area Network) by ETIS (European Telecommunication Standards Institute), the wireless LAN standard by IEEE (Institute of Electrical & Electronics Engineers), and recent developments in the Bluetooth consortium.
In addition, a public network-based wireless LAN service, known as the next generation wire/wireless integrated communication technology, will be the a core issue of the future communication markets. It is expected that the wireless LAN will cause a qualitative change in information technology (IT) industries. In particular, the public network-based wireless LAN is expected to cause quantitative growth of related industries because it aims to support mobile nodes such as a notebook computer and a personal digital assistant (PDA). Among others, an IEEE 802.11 wireless LAN is in the spotlight of the wireless LAN field, and is one of the more popularly used technologies.
In the mobile ad hoc network, connection between mobile nodes is made using peer-to-peer level multi-hopping technology. Such technology has many problems to solve because it needs to be able to dynamically change a network topology and achieve self forming and self healing. In the mobile ad hoc network, ad-hoc routing is important and is technology that must be necessarily supported before a certain application is installed in the mobile ad hoc network. In addition, route discovery of the ad-hoc routing is core technology used for forming the mobile ad hoc network.
In a current method of forming a mobile ad hoc network using AODV (Ad Hoc On-Demand Distance Vector) protocol, when a source node desires to communicate with a destination node, route discovery is performed by the source node if there is no information on the destination node. Here, the AODV protocol is a typical on-demand routing protocol in the mobile ad hoc network, and is a routing technique for generating a route when a source node sends a data transmission request to a destination node. At this point, all nodes in the mobile ad hoc network maintain information on only the route via which data is transmitted, in a routing table. A source node desiring to send data discovers, or searches for the shortest route to a destination node on an on-demand basis, through a route discovery procedure.
In the AODV protocol, there are four types of messages used for route discovery and maintenance. The four messages include Route Request (RREQ), Route Reply (RREP), Route Error (RERR), and Route Reply Acknowledgement (RREP-ACK).
The RREQ is a message used by a source node to discover (search) a destination node, i.e., to request route generation. The RREP is a response message to the RREQ. That is, if a node receiving the RREQ itself is a destination node or knows a route path to a destination node, it transmits an RREP message to a node that first transmitted the RREQ (hereinafter, referred to as an RREQ source node), in response to the RREQ message on a unicast basis.
The RREP-ACK is a message used by an RREQ source node receiving the RREP to respond to the received RREP message. The RERR is a message used to notify a source node of route disconnection when a route to a destination node is disconnected. Here, a source node receiving the RERR starts a new route discovery procedure in order to generate a new route to the destination node.
FIG. 1 is a diagram illustrating a procedure for performing route discovery in an AODV protocol. A source node 10 transmits a RREQ message to a destination node 20 in order to set up a route to the destination node 20. If the source node 10 transmits the RREQ, nodes which are not the destination node 20 or have no information on the destination node 20 forward the RREQ to their neighbor nodes. After the RREQ is forwarded to the neighbor nodes, a reverse path to the source node 10 is formed.
If a node receiving the RREQ is a destination node or an intermediate node having information on the destination node, it sends a RREP message to the source node 10, or an RREQ source node. The intermediate node sends the RREP having information on the destination node to the RREQ source node 10, using a reverse path formed with the RREQ. If the RREQ source node 10 receives the RREP, a forward path to the intermediate node is formed, completing route discovery. In this way, a route path between the source node 10 and the destination node 20 is completed through intermediate nodes 12, 14 and 16 that transmitted and received the RREQ and the RREP messages.
In the above process, if a procedure for requesting a RREP by sending a RREQ has occurred in a unidirectional link, a corresponding node may fail to transmit the RREP even though it has received the RREQ. If no RREP generated by the same route discovery can arrive at the RREQ source node 10, the RREQ source node 10 re-attempts the route discovery after a lapse of a predetermined time.
In this case, the RREQ source node 10 repeatedly performs the same route discovery operation without any modifications. Therefore, even though the RREQ source node 10 repeatedly re-attempts the route discovery, it will fail to discover and set up a route path. In this case, if any recovery operation is not performed between the source node 10 and the destination node 20, there is a high possibility that the above problem will occur even though there is another bidirectional route available between the source node 10 and the destination node 20.
In order to solve such a problem, in the existing AODV protocol, when a node fails to transmit the RREP message, the corresponding node stores a next-hop node for the failed RREP in a black list. In addition, the node disregards a RREQ message received from a node in the black list, and removes the node in the black list after a lapse of a predetermined time.
Such a unidirectional link formed between nodes causes a long time delay as well as potentially a fatal difficulty in completing the route discovery procedure. Although the method of generating a black list in order to solve this problem in the existing AODV protocol can avoid a unidirectional link, it must repeatedly perform route discovery on the same route path. Such a method using a black list deteriorates efficiency of a mobile ad hoc network because a time period actually required for forming a route is increased due to the occurrence of many route paths.
FIG. 2 is a diagram illustrating a method for solving problems occurring due to a unidirectional link in the existing AODV protocol. In the drawing, the number of arrows is identical to a transmission count (or transmission number) of RREQ messages and RREP messages used to form a route path by completing route discovery.
In order to resolve the problem occurring due to the unidirectional link, conventionally, an intermediate node 36 includes a next hop node 35 to which it intended to send the RREP message, in a black list, and disregards RREQ messages transmitted from nodes in the black list. Thereafter, the source node 30 again performs route discovery from the beginning by re-sending a route request to the desired destination node 40.
Therefore, because the node 36 having a black list does not receive a RREQ from the node 35 connected with a unidirectional link when the route discovery procedure is performed again, the AODV protocol does not strive to form a route passing through the node 35 included in a black list and the node 36 having a black list. However, the source node 30 must again perform a route request operation on the desired destination node from the beginning. That is, the conventional route discovery method improved to resolve the unidirectional link problem performs again the entire route discovery each time an error occurs, raising another problem that RREQ and RREP messages which become overhead on the entire network are frequently transmitted over the entire network and the network performance is deteriorated due to the number of unnecessary duplicate RREQ and RREP messages.
If the route discovery procedure is performed again, the source node 30 discards the previously performed route discovery procedure. In such a conventional method, RREQ and RREP messages which are regarded as overhead in terms of throughput of the network are unnecessarily transmitted several times, causing deterioration in route discovery performance. In addition, the conventional method requires a long time delay in performing route discovery, deteriorating efficiency of a mobile ad hoc network. In particular, the conventional method may have a fatal problem when there are several nodes in the mobile ad hoc network.